package com.sicheng.蓝桥.练习题.基础图论.迷宫系列;

import java.io.*;
import java.util.ArrayDeque;

/**
 * @author zsc
 * @version 1.0
 * @date 2022/5/20 9:20
 */
public class 走迷宫 {
    /**
     * 给定一个n*m的二维整数数组，用来表示一个迷宫，数组中只包含0或1，其中0表示可以走的路，1表示不可通过的墙壁。
     * <p>
     * 最初，有一个人位于左上角(1, 1)处，已知该人每次可以向上、下、左、右任意一个方向移动一个位置。
     * <p>
     * 请问，该人从左上角移动至右下角(n, m)处，至少需要移动多少次。
     * <p>
     * 数据保证(1, 1)处和(n, m)处的数字为0，且一定至少存在一条通路。
     * <p>
     * 输入格式
     * <p>
     * 第一行包含两个整数n和m。
     * <p>
     * 接下来n行，每行包含m个整数（0或1），表示完整的二维数组迷宫。
     * <p>
     * 输出格式
     * <p>
     * 输出一个整数，表示从左上角移动至右下角的最少移动次数。
     * <p>
     * 数据范围
     * <p>
     * 1≤n,m≤100
     * <p>
     * 样例
     * 输入样例：
     * 5 5
     * 0 1 0 0 0
     * 0 1 0 1 0
     * 0 0 0 0 0
     * 0 1 1 1 0
     * 0 0 0 1 0
     * 输出样例：
     * 8
     * <p>
     * 链接：https://www.acwing.com/solution/content/2078/
     *
     * @param args a
     */

    static int n;
    static int m;
    static int[][] g;

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        BufferedWriter writer = new BufferedWriter(new OutputStreamWriter(System.out));
        String line = reader.readLine();
        n = line.charAt(0) - '0';
        m = line.charAt(2) - '0';

        g = new int[n + 1][m + 1];
        for (int i = 1; i <= n; i++) {
            String[] nums = reader.readLine().split(" ");
            for (int j = 1; j <= m; j++) {
                g[i][j] = Integer.parseInt(nums[j - 1]);
            }
        }

        bfs();
        writer.write(String.valueOf(g[n][m] - 1));
        writer.flush();
        reader.close();
        writer.close();
    }


    static int[][] d = {
            {1, 0},
            {-1, 0},
            {0, -1},
            {0, 1}
    };

    private static void bfs() {
        ArrayDeque<int[]> deque = new ArrayDeque<>();
        deque.offer(new int[]{1, 1});
        g[1][1] = 1;
        while (!deque.isEmpty()) {
            int[] e = deque.poll();

            for (int i = 0; i < 4; i++) {
                int x = e[0] + d[i][0];
                int y = e[1] + d[i][1];

                if (x >= 1 && x <= n && y >= 1 && y <= m && g[x][y] == 0) {
                    g[x][y] = g[e[0]][e[1]] + 1;
                    deque.offer(new int[]{x, y});
                    if (x == n && y == m)
                        return;
                }
            }
        }
    }
}
